1. Field of the Invention
The present invention relates to an image coding device and an image decoding device, and particularly to lossless coding/decoding and lossy coding/decoding effected on an input image expressed in multivalues.
2. Description of the Related Art
Arithmetic coding is a kind of entropy coding and shows a high-efficiency coding method wherein a coding ratio (hereinafter abbreviated as "C/R") is brought closer to entropy under the process of steady probability as input data increases. As an example using the arithmetic coding in practice, JBIG (Joint Bi-level Image Group) is known which is the international standard of binary lossless coding. In the JBIG, an improvement in C/R has been made by adding state division using pixels for reference to the arithmetic coding. At this time, a combination of values of one or plural reference pixels will be called "context" below. Further, a combination of the context and the value of the pixel to be coded will be called "state" below.
In general, the arithmetic coding is often used as a coding method for handling binary data. However, there is now a growing demand for coding of a multivalued image with the advancement of image processing technology. Correspondingly, it has inevitably been desired that the arithmetic coding is also applied to the multivalued image.
When a multivalued image is compressed by the normal arithmetic coding, a process of converting it from multivalue data to binary data is required as a preprocess. This has been described in, for example, a reference entitled "International Standard for Multimedia Coding" edited by Hiroshi Yasuda, Maruzen, p. 80. When the multivalued image is compressed in accordance with the JBIG system, for example, a bit plane method or the like of slicing multivalue data bits and capturing them as binary data has been considered.
However, on the other hand, it is known that the handling of the image data as multivalued symbols rather than attempting to divide the image data into the bit planes is good in efficiency to compress the multivalued image. In view of these circumstances, a method of extending the arithmetic coding so as to be able to deal with the multivalued data as it is, has been proposed. This has been described on page 81 in the above-described reference, for example. In the binary arithmetic coding, the number line is divided into two to obtain codes. On the other hand, the extension of the data to the multivalues can be easily carried out by increasing the number of divisions of the number line.
FIG. 3 is a configurational view showing one example of a conventional coding device using a multivalue arithmetic coding method. In the drawing, reference numerals 1, 3, 4, 5, 6, 11, 14, 15, 16 and 17 respectively indicate an image input unit, an image analyzer, a probability estimate unit, a coding unit, a code output unit, image data, status data, probability estimated data, coded data and pixel-value data. Incidentally, the present drawing and FIG. 4 are ones obtained by suitably changing words or the like by reference to FIG. 1 in "IBM Journal of Research and Development," Vol. 32, No. 6, p. 754, 1988.
The coding device comprises the image input unit 1, the image analyzer 3, the probability estimate unit 4, the coding unit 5, and the code output unit 6. The image input unit 1 receives an input image from the outside and sends it to the image analyzer 3 as the image data 11. The image analyzer 3 receives the image data 11 therein and sends the value of a pixel to be coded to the coding unit 5 as the pixel-value data 17. Further, when reference is made to a peripheral pixel, the image analyzer 3 sends the value of the reference pixel to the probability estimate unit 4 as the status data 14. The probability estimate unit 4 receives the status data 14 therein and sends the probability estimated data 15 corresponding to the status data 14 to the coding unit 5. Thereafter, the probability estimate unit 4 updates the probability estimated data held therein. The coding unit 5 creates a codeword from the probability estimated data 15 and the pixel-value data 17 and sends it to the code output unit 6 as the coded data 16. The code output unit 6 outputs the coded data 16 as an output code.
FIG. 4 is a configurational view showing one example of a conventional decoding device using a multivalue arithmetic coding method. In the drawing, reference numerals 21, 22, 23, 24, 26, 31, 33, 34, 36 and 37 respectively indicate a code input unit, a codeword analyzer, an image analyzer, a probability estimate unit, an image output unit, coded data, status data, probability estimated data, image data and pixel-value data.
The code input unit 21 receives an input code from the outside and sends it to the codeword analyzer 22 as the coded data 31. The codeword analyzer 22 decodes the coded data 31 using the probability estimated data 34 sent from the probability estimate unit 24. Further, the codeword analyzer 22 sends the pixel-value data 37 corresponding to the result of decoding to the image analyzer 23. The image analyzer 23 creates an output image from the pixel-value data 37 and sends it to the image output unit 26 as the image data 36. When reference is made to each peripheral pixel, the image analyzer 23 sends the value of the pixel for reference to the probability estimate unit 24 as the status data 33. The image output unit 26 outputs the image data 36 to the outside as an output image.
The operation of the coding device based on the above construction will be described. FIG. 5 is a flowchart for describing one example of the operation of the general coding device. In S41, an image is first input to the image input unit 1. The image input unit 1 sends the result of input to the image analyzer 3 as the image data 11. In S42, the values of predetermined pixels for reference are integrated into a context by the image analyzer 3. In S43, the image analyzer 3 sends the status data 14 obtained by adding the value of each pixel to be coded to the context determined in S42 to the probability estimate unit 4. Next, the probability estimate unit 4 generates the probability estimate data 15 based on data about the context in the status data 14 and sends it to the coding unit 5. In S44, the coding unit 5 creates the coded data 16 from the probability estimate data 15 and the pixel-value data 17 by using the arithmetic coding method. In S45, the code output unit 6 outputs the coded data 16 to the outside. In S46, the probability estimate unit 4 updates data corresponding to the status data 14, of the probability estimate data stored in the probability estimate unit 4. At this time, the probability estimate unit 4 brings other probability estimate data up to date if necessary. It is judged in S47 whether all the input image data 11 have been coded. If the answer is found to be Yes in S47, then the routine procedure is terminated. If the answer is found to be No in S47, then the routine procedure is returned to S41 where non-processed data is subjected to the coding processing.
FIG. 6 is a flowchart for describing one example of the operation of the general decoding device. In S51, a code is first input to the code input unit 21. The input code is sent to the codeword analyzer 22 as the coded data 31. In S52, the values of predetermined pixels for reference are obtained from the pixel-value data 37 outputted from the codeword analyzer 22 and they are combined together to determine a context. In S53, the status data 33 obtained by adding an estimated value of a pixel to be coded to the context determined in S52 is sent to the probability estimate unit 24. The probability estimate unit 24 generates the probability estimated data 34 based on data about the context in the status data 33 and sends it to the codeword analyzer 22. In S54, the codeword analyzer 22 produces the pixel-value data 37 from the status data 34 and the coded data 31 by the decoding method using the arithmetic coding. In S55, the image analyzer 23 sends the pixel-value data 37 to the image output unit 26 as the image data 36. Further, the image output unit 26 outputs the image data 36 to the outside as an output image. It is judged in S57 whether all the input coded data 31 have been decoded. If it is judged in S57 that all the coded data 31 have been decoded, then the routine procedure is completed. If it is judged in S57 that non-processed data exists, then the routine procedure is returned to S51 where the non-processed data is subjected to the decoding processing.
Incidentally, portions surrounded by broken lines in FIGS. 5 and 6 respectively indicate the process common to the coding and decoding processes. In the above-described operation, the determination of the contexts in S42 and S52 is performed using the predetermined pixels for reference. At this time, the reference pixels may be adaptably changed according to the property of an image.
This multivalue arithmetic coding method has several problems. Such problems will next be described. The first problem is that a high calculation accuracy is required. This results from an increase in the number of divisions of the number line. Although a commonly-used computer is enough to provide the accuracy of calculation necessary for arithmetic coding, a serious problem arises when the calculation accuracy is speeded up under its reduction.
Since 2.sup.8 =256 kinds of data are considered when, for example, 8-bit image data is directly handled, a procedure for dividing the number line into 256 and selecting one of them is required. If simply calculated, accuracies as high as about 100 times are required as compared with 1-bit data that may be divided into two.
Second and third problems result from the fact that the number of states suddenly increases in the case of the multivalue arithmetic coding as compared with the binary arithmetic coding. FIG. 7 is a view for describing a comparison between the number of states. Although the use of pixels for reference is an effective means for improving the C/R, the more the number of the reference pixels increases, the more the number of the states greatly increases correspondingly. JBIG makes use of the number of states corresponding to 2.sup.12 =4096 as shown in FIG. 7, which is produced by setting the number of the reference pixels to 10 and making a further division of four states. However, if the same processing is effected on a 8-bit image, then the number of states reaches about 8.times.10.sup.28. Even if the number of the pixels for reference is defined as two, the number of states reaches about 17 million as shown in FIG. 7.
The following two points are mentioned as specific problems incident to the increase in the number of states.
Large-capacity memories corresponding to the number of states are necessary. * It is difficult to estimate the probability of appearance of each state.
Since the number line is divided according to the probability of occurrences of respective states in the case of the arithmetic coding method, it is necessary to prepare memories for storing therein the probability of occurrences of the respective states. Therefore, when the number of the states increases, large-capacity memories corresponding to the number of the states are required. Further, since the number of the states increases as compared with the number of pixels of the image data used as the input data, it is difficult to estimate the probability that the respective states appear.
The reduction in the number of the states is directly linked with the reduction in C/R as it is. However, when a systematic restriction such as hardware or the like exists, there is a case in which it is desired to reduce the number of states even by making a reduction in efficiency. In the study on realization of such multivalue arithmetic coding, a method of omitting states in which an influence exerted on C/R is low and reducing the number of states to a less number of states is common. This operation is called "degeneracy."
Since the problem on the memory's capacity and the problem that it is difficult to estimate the probability of appearance of the states, result from the excessive increase in the number of states, both problems can be resolved simultaneously if it is possible to reduce the number of the states. As an example of such a study, there is known, for example, IEICE Technical Report, IE80-108 edited by Kato and Yasuda, entitled "A state degeneration method for source encoding of multi-level images". However, the degeneracy of the states basically needs a process of selecting states to be deleted. In the method of determining parameters for the degenerating method according to the image as described in the present reference, the load on the degeneration process is large.
A stationary degenerating system has been used in the reference entitled "High-Efficiency Coding System for Continuous-tone Image" by Imanaka, Ueno, Semasa and Tabe at the 1982 national meeting of Communication Department of IECE, S3-8. Since an assumption is made to the property of an image when such a stationary degenerating system is used, the dependence of C/R on the image is placed under apprehension.
Although there is a difference between the two systems according to the method due to the execution of the degeneration process, a problem arises that the reduction in C/R cannot be avoided in principle. This problem is unavoidable due to the conditions such as the systematic restrictions, but another problem is due to the degeneration process itself other than the multivalue arithmetic coding method. Further, the degeneration process cannot resolve the above-described problem on the accuracy of calculation.